package _17_剑指Offer;

public class _58_剑指Offer翻转单词顺序 {

    public static void main(String[] args) {

        String str = " ";
        _58_剑指Offer翻转单词顺序 v = new _58_剑指Offer翻转单词顺序();

        System.out.println(v.reverseWords(str));

    }

    public String reverseWords(String s) {
        // 取出首位空格
        String[] newStr = s.trim().split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = newStr.length - 1; i >= 0; i--) {

            if ("".equals(newStr[i])) continue;

            sb.append(newStr[i]).append(" ");
        }
        return sb.toString().trim();
    }

    public String reverseWords1(String s) {
        char[] chars = s.toCharArray();

        char[] newChar = new char[chars.length];
        int index = 0;
        boolean isWord = false;
        for (char cur : chars) {
            if (!isWord && cur == ' ') continue;
            if (cur != ' ') {
                newChar[index++] = cur;
                isWord = true;
            } else {
                newChar[index++] = ' ';
                isWord = false;
            }
        }

        int len = isWord? index: index - 1;
        // 翻转整个单词
        swap(0, len - 1, newChar);

        // 翻转单个单词
        int left = 0;
        for (int i = 0; i < len; i++) {
            if (newChar[i] == ' ') {
                swap(left, i - 1, newChar);
                left = i + 1;
            }
        }
        // 翻转最后一个单词
        swap(left, len - 1, newChar);
        return len < 0? "": new String(newChar, 0, len);
    }

    public void swap(int begin, int end, char[] chars) {
        while (begin < end) {
            char temp = chars[begin];
            chars[begin++] = chars[end];
            chars[end--] = temp;
        }
    }

}
